package leetcode.greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;


/**
 * 
 * @author 26233
 * 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

 

示例：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
 

提示：

S的长度在[1, 500]之间。
S只包含小写字母 'a' 到 'z' 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-labels
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode763_PartitioanLabels {
	
	/**
	 * 
	 * 绕路解法：
	 * 	1、得到每个字母的开始和最后出现的位置
	 * 	2、对1中的结果以开始下标排序
	 * 	3、从最小的开始合并判断，开始下标小于当前段结束坐标的必在一个段中，并且更新段结束下标
	 * 
	 * @param s
	 * @return
	 */
	public static List<Integer> partitionLabels(String s) {

		int[][] charArr = new int[26][2];
		char[] sCharArr = s.toCharArray();
		for(int i = 0; i < sCharArr.length; i++) {
			int index = sCharArr[i] - 'a';
			if(charArr[index][0] == 0) {// 新出现的字符
				charArr[index][0] = i + 1;
			}else {
				charArr[index][1] = i + 1;
			}
		}
		
		for(int i = 0; i < charArr.length; i++) {
			if(charArr[i][0] != 0 && charArr[i][1] == 0) {
				charArr[i][1] = charArr[i][0];
			}
		}
		
		Arrays.sort(charArr, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});
		
		int index = 0;
		while(charArr[index][0] == 0) {
			index++;
		}
		
		List<Integer> result = new ArrayList<Integer>();
		while(index < charArr.length) {
			int[] fir = charArr[index];
			index++;

			while(index < charArr.length) {
				if(charArr[index][0] < fir[1]) {
					if(charArr[index][1] > fir[1])
						fir[1] = charArr[index][1];
					index++;
				}else {
					result.add(fir[1] - fir[0] + 1);
					break;
				}
			}

			
			if(index == charArr.length) {
				result.add(fir[1] - fir[0] + 1);
			}
		}
		
		return result;
    }
	
	/**
	 * 简洁的解法:
	 * 		1、第一遍遍历，记录字母的最后出现位置
	 * 		2、第二次遍历，每次遍历一个字母更新一次该段的最终位置，如果遍历下标等于该段的最终位置，则得到本段长度，开始计算下一段
	 * 		3、效率不高
	 * @param s
	 * @return
	 */
	public static List<Integer> partitionLabels2(String s) {
		
		int[] charLastIndex = new int[26];
		for(int i = 0;i < s.length(); i++) {
			charLastIndex[s.charAt(i) - 'a'] = i;
		}
		
		int segStartIndex = 0,segLastIndex = 0;
		List<Integer> result = new ArrayList<>();
		for(int i = 0; i < s.length(); i++) {
			segLastIndex = Math.max(segLastIndex, charLastIndex[s.charAt(i) - 'a']);
			
			if(segLastIndex == i) {
				result.add(segLastIndex - segStartIndex + 1);
				segStartIndex = i + 1;
			}
		}
		
		return result;
	}
	
	public static void main(String[] args) {
		
		// String s = "ababcbacadefegdehijhklij";
		String s = "ababcbacadefegdehij";
		// String s = "a";
		partitionLabels2(s);
		
	}

}
